/*
 * @lc app=leetcode.cn id=234 lang=java
 *
 * [234] 回文链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    /**
     * Accepted
    88/88 cases passed (4 ms)
    Your runtime beats 81.02 % of java submissions
    Your memory usage beats 54.06 % of java submissions (57.5 MB)
     */
    public boolean isPalindrome(ListNode head) {
        int len = 0;
        ListNode cur = head;
        while (cur != null) {
            len++;
            cur = cur.next;
        }
        if (len <= 1)
            return true;

        int mid = len / 2;

        cur = head;
        for (int i = 0; i < len - mid; i++) {
            cur = cur.next;
        }

        ListNode reverse = null;
        while (cur != null) {
            ListNode tmp = cur.next;
            cur.next = reverse;
            reverse = cur;
            cur = tmp;
        }

        cur = head;

        for (int i = 0; i < mid; i++) {
            if (cur.val != reverse.val)
                return false;
            cur = cur.next;
            reverse = reverse.next;
        }
        return true;
    }

        /**
     * Accepted
    88/88 cases passed (7 ms)
    Your runtime beats 48.96 % of java submissions
    Your memory usage beats 65.88 % of java submissions (56.1 MB)
     */
    public boolean isPalindrome2(ListNode head) {
        ListNode cur = head;
        ListNode reverse = reverseList(head);
        while (cur != null && reverse != null) {
            if (cur.val != reverse.val)
                return false;
            cur = cur.next;
            reverse = reverse.next;
        }
        if (cur == null && reverse == null)
            return true;
        return false;
    }

    private ListNode reverseList(ListNode head) {
        ListNode dummy = new ListNode();
        ListNode cur = head;
        while (cur != null) {
            dummy.next = new ListNode(cur.val, dummy.next);
            cur = cur.next;
        }
        return dummy.next;
    }
}
// @lc code=end
